package DataStructure.graph;

import DataStructure.UFSet;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;


//无向加权图
public class WGraph {
    private int V;//顶点数量
    private int E;//边数量
    private Deque<Edge> edge;//边
    private int[] degree;//顶点的度
    private Deque<Edge>[] adj;//邻接表


    public WGraph(int v) {
        V=v;
        E=0;
        edge=new ArrayDeque<>();
        degree=new int[v];
        adj=new ArrayDeque[v];
        for (int i = 0; i < adj.length; i++) {
            adj[i]=new ArrayDeque<>();
        }
    }

    public Deque<Edge> near(int v) {
        return adj[v];
    }

    public void addEdge(int v,int w,double weight){
        Edge e=new Edge(v,w,weight);
        Edge e2=new Edge(w,v,weight);
        if(adj[v].contains(e)||adj[v].contains(e2))
            return;
        edge.add(e);
        degree[v]++;
        degree[w]++;
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }


    //最小生成树
    Deque<Edge> edges;//存储最小生成树的所有边
    int dis;//所有权重和
    PriorityQueue<Edge> pq;//存储横切边
    //prim算法
    public Deque<Edge> prim(){
        edges=new ArrayDeque<>();
        dis=0;
        pq=new PriorityQueue<>((o1, o2) -> (int) (o1.weight()-o2.weight())) ;
        boolean[] mark=new boolean[V];//是否访问过该顶点
        visit(0,mark);//从0点开始
        //当所有顶点加入后没有横切边
        while (!pq.isEmpty()){
            Edge tmp=pq.poll();//最小权重的边
            int in=tmp.from();//其中一个顶点
            int out=tmp.to();//另一个顶点
            //判断是否为横切边,当两个顶点在不同部分
            if(mark[out]^mark[in]){
                edges.offer(tmp);
                dis+=tmp.weight();
                if(mark[in]) visit(out,mark);
                else visit(in,mark);
            }
        }
        return edges;
    }
    private void visit(int v,boolean[] mark){
        mark[v]=true;
        //添加顶点的横切边
        if(near(v)!=null){
            for (Edge e : near(v)) {
                if(!mark[e.to()])//如果未访问添加到pq中排序
                    pq.offer(e);
            }
        }
    }

    //kruskal算法
    public Deque<Edge> kruskal(WGraph G){
        edges=new ArrayDeque<>();
        dis=0;
        pq=new PriorityQueue<>((o1, o2) -> (int) (o1.weight()-o2.weight()));
        UFSet uf=new UFSet(G.V);//并查集
        //将所有边添加到队列中排序
        for (Edge e : G.edges) {
            pq.offer(e);
        }
        //当添加到n-1条边时停止
        while (edges.size()<G.V-1){
            Edge e=pq.poll();//每次选出最小权重边
            int v=e.from();
            int w=e.to();
            //判断两个顶点是否已经加入树中
            if(!uf.isConnected(v,w)){
                uf.union(v,w);
                edges.offer(e);
                dis+=e.weight();
            }
        }
        return edges;
    }



}
